/*
这是一个接受通用指针参数的环形链表
*/

#include "cirular_link.h"
#include <stdlib.h>

// 结构体已经对文件作用域之外隐藏, 在main函数中无法直接拿到data
struct link_node_t {
  void *data;
  link_node next;
};

struct link_t {
  link_node head;
  link_node tail;
  size_t size;
};

clink link_create() {
  clink link;
  if ((link = malloc(sizeof(struct link_t))) == NULL)
    return NULL;

  link->head = link->tail = NULL;
  link->size = 0;

  return link;
}

void link_clear(clink l) {
  while (l->head != l->tail) {
    l->tail->next = l->head->next;
    free(l->head);
    --l->size;
  }
  // 仅剩一个对象了
  free(l->head);
  l->head = l->tail = NULL;
  l->size = 0;
}

void link_destory(clink l) {
  link_clear(l);
  free(l);
}

bool add_to_link(clink l, void *val) {
  link_node node = malloc(sizeof(struct link_node_t));
  if (node == NULL)
    return false;

  node->data = val;
  // 空表
  if (l->head == NULL && l->tail == NULL) {
    node->next = node; // 节点自循环
    l->head = l->tail = node;
  } else { // 尾插
    node->next = l->head;
    l->tail->next = node;
    l->tail = node;
  }
  ++l->size;
  return true;
}

bool delete_from_link(clink l, void *val) {
  if (l->head == NULL)
    return false;

  link_node prev = NULL, cur = l->head;
  for (; prev != l->tail; prev = cur, cur = cur->next) {
    if (cur->data == val)
      break;
  }
  // 删除的元素不存在
  if (prev == l->tail)
    return false;

  // 表头第一个对象并且仅一个元素
  if (prev == NULL && l->head == l->tail) {
    free(cur);
    l->head = l->tail = NULL;
  } else if (prev == NULL) {   // 表头第一个对象
    l->tail->next = cur->next; // 断链
    l->head = cur->next;       // 更新头指针
    free(cur);
  } else if (cur == l->tail) {
    prev->next = cur->next; // 断链
    l->tail = prev;         // 更新尾指针
    free(cur);
  } else { // 一般情况
    prev->next = cur->next;
    free(cur);
  }

  --l->size;
  return true;
}

link_node search_link(clink l, void *val) {
  link_node p = l->head;

  if (p == NULL)
    return false;

  do {
    if (p->data == val)
      return p;

    p = p->next;
  } while (p != l->head);

  return NULL;
}

size_t link_length(clink l) { return l->size; }

/*
节点数据在文件作用域之外时无法访问的.
该函数通过函数指针提供了一个遍历链表节点数据的接口
通过自定义函数, 可以灵活处理节点中数据的呈现方式.
*/
void link_transver(clink l, void (*visit)(void *data)) {
  if (l->head == NULL)
    return;

  link_node node = l->head;

  do {
    // node->data 会通过参数的形式复制给自定义函数
    (*visit)(node->data);
    node = node->next;
  } while (node != l->head);
}